package day002;

import java.util.ArrayList;
import java.util.List;

public class CoinChange {
    public static void main(String[] args) {
        List<Integer> coins = new ArrayList<>();
        coins.add(1);
        coins.add(2);
        coins.add(5);
        System.out.println(coinChange(coins, 11, 11));
    }


    static int coinChange(List<Integer> coins, int amount, int n) {

        if (n == 0) return 0;
        if (n <= -1) return -1;
        Integer res = Integer.MAX_VALUE;
        for (Integer coin : coins) {
            int subproblem = coinChange(coins, amount, n - coin);
            if (subproblem == -1) continue;
            res = Integer.min(res, 1 + subproblem);

        }
        if (res != Integer.MAX_VALUE) {
            return res;
        } else {
            return -1;
        }
    }
}
